#include <bits/stdc++.h>
using namespace std;

// 【题目】42. 接雨水
// 【难度】困难
// 【提交】2025.9.25 https://leetcode.cn/problems/trapping-rain-water/submissions/665973323
// 【标签】单调栈
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for(int i = 0; i < n; ++i){
            while(!stk.empty() && height[i] >height[stk.top()]){
                int top = stk.top();
                stk.pop();
                if(stk.empty()){
                    break;
                }
                int left = stk.top();
                int Width = i - left - 1;
                int Height = min(height[left], height[i]) - height[top];
                ans += Width *Height;
            }
            stk.push(i);
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 还是单调栈，做过了模板题I，II，III，这道题已经小菜一碟了；
*/


/*
--------------------------------------------------------------------------------------------------------------
（学习笔记：LeetCode 42「接雨水」
（提交记录：2024-03-25，C++，用时 12 ms，内存 7.3 MB）

一、题意与模型
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，要求计算按此排列的柱子，下雨之后能够接多少雨水。每个柱子的宽度均为 1，雨水会根据柱子的高度进行积累。

二、标准 DP 状态设计
设 dp[i] 表示第 i 列柱子上能接的最大雨水量。每一列接的水量由其两侧的最大高度所决定，即左侧和右侧的最大高度的最小值减去该柱子的高度。接的雨水量计算公式为：water[i] = min(maxLeft[i], maxRight[i]) - height[i]。
但考虑到我们要高效处理此问题，采用 单调栈 技术，避免冗余的额外空间和计算。

三、你的实现思路
单调栈的思想：栈用于保存尚未计算出能接水的柱子索引。每当遇到一个比栈顶元素更高的柱子时，意味着可以计算出栈顶元素能接的水量。
水量计算：对于每个弹出栈的柱子，计算它能够接的水量，水量由当前柱子的高度和栈顶柱子两侧的柱子之间的高度差决定。
效率：通过栈高效地计算水量，每个柱子最多进栈和出栈一次，保证时间复杂度为 O(n)。

四、逐行注释（带细节提醒）
cpp

class Solution {
public:
int trap(vector<int>& height) {
int ans = 0; // 用于存储最终的接水量
stack<int> stk; // 栈，用于保存柱子的索引
int n = height.size(); // 获取柱子的数量

arduino

    // 遍历所有柱子
    for (int i = 0; i < n; ++i) {
        // 当栈不为空且当前柱子比栈顶的柱子高时，开始计算能接多少水
        while (!stk.empty() && height[i] > height[stk.top()]) {
            int top = stk.top();  // 获取栈顶元素的索引
            stk.pop();             // 弹出栈顶元素
            if (stk.empty()) {
                break;            // 如果栈为空，说明没有形成“槽”，跳出循环
            }
            int left = stk.top();  // 获取栈顶的新元素索引
            int Width = i - left - 1;  // 计算当前槽的宽度
            int Height = min(height[left], height[i]) - height[top];  // 计算槽的高度
            ans += Width * Height;   // 计算该槽的接水量并累加
        }
        stk.push(i);  // 将当前柱子的索引压入栈中
    }
    return ans;  // 返回最终的接水量
}
};

五、正确性证明
使用栈保证了每个柱子只能被访问和计算一次，栈中元素始终保持递增顺序。每次弹栈时，我们都能计算出前一个柱子能够接的水量。
通过计算左右两侧的最大高度，准确地计算出每个柱子接的水量，避免了暴力求解的 O(n²) 时间复杂度。

六、复杂度
时间：O(n)，每个元素最多被入栈和出栈一次，因此时间复杂度为 O(n)。
空间：O(n)，栈最多保存 n 个元素，即柱子的索引。

七、优缺点分析
优点：
时间复杂度为 O(n)，能够高效地处理大规模数据。
使用栈有效地减少了空间复杂度，相比动态规划避免了额外的数组存储。

缺点：
栈操作对理解要求较高，尤其是在计算水量时的逻辑。
对于一些边界情况（如没有柱子的情形），需要在其他地方进行优化处理。

八、改进建议
当前算法的时间复杂度已经最优，进一步优化空间复杂度时可以考虑空间较小的栈优化。
代码可以增加注释，帮助理解栈操作的细节，提升可读性。

九、一句话总结
该题通过单调栈的应用，高效地计算了柱子能接的水量，时间复杂度为 O(n)，空间复杂度为 O(n)，是一种高效解决接雨水问题的经典方法。
--------------------------------------------------------------------------------------------------------------
*/